// Philos.java

// This application avoids deadlock by preventing the scenario in which all
// philosophers simultaneously pick up their left chopsticks before picking
// up their right chopsticks. Four philosophers always first pick up their
// left chopsticks, and the remaining philosopher always first picks up the
// right chopstick.

// This application avoids starvation, where one or more philosophers never
// eat because adjacent philosophers are always eating, by assigning random
// thinking and eating times to each philosopher.

public class Philos
{
   public static void main (String [] args)
   {                                                 
      ChopStick cs1 = new ChopStick (0);
      ChopStick cs2 = new ChopStick (1);
      ChopStick cs3 = new ChopStick (2);
      ChopStick cs4 = new ChopStick (3);
      ChopStick cs5 = new ChopStick (4);

      Philosopher p1 = new Philosopher ("P1", cs1, cs5);
      Philosopher p2 = new Philosopher ("P2", cs2, cs1);
      Philosopher p3 = new Philosopher ("P3", cs3, cs2);
      Philosopher p4 = new Philosopher ("P4", cs4, cs3);
      Philosopher p5 = new Philosopher ("P5", cs5, cs4);

      p1.start ();
      p2.start ();
      p3.start ();
      p4.start ();
      p5.start ();
   }
}

class ChopStick
{
   private int id;

   private boolean isTaken;

   ChopStick (int id)
   {
      // Assign an id number to this ChopStick.

      this.id = id;
   }

   synchronized void get ()
   {
      while (isTaken)
         try
         {
            wait ();
         }
         catch (InterruptedException e)
         {
         }

      isTaken = true;
   }

   int getID ()
   {
      return id;
   }

   synchronized void put ()
   {
      isTaken = false;

      notify ();
   }
}

class Philosopher extends Thread 
{
   private String name;
   private ChopStick left, right;

   Philosopher (String name, ChopStick left, ChopStick right)
   {
       this.name = name;
       this.left = left;
       this.right = right;
   }

   public void run ()
   {
       while (true)
       {
          try
          {
              System.out.println ("Philosopher " + name + " is thinking.");
               
              sleep((int) (100 * Math.random ()));

              System.out.println ("Philosopher " + name + " is hungry.");

              // Acquire lowest-numbered chopstick.

              if (left.getID () < right.getID ())
              {
                  System.out.println ("Philosopher " + name +
                                      " getting left chopstick.");
                  left.get ();

                  System.out.println ("Philosopher " + name +
                                      " got left chopstick.");
              }
              else
              {
                  System.out.println ("Philosopher " + name +
                                      " getting right chopstick.");
                  right.get ();

                  System.out.println ("Philosopher " + name +
                                      " got right chopstick.");
              }

              // Acquire other chopstick.

              if (left.getID () < right.getID ())
              {
                  System.out.println ("Philosopher " + name +
                                      " getting right chopstick.");
                  right.get ();

                  System.out.println ("Philosopher " + name +
                                      " got right chopstick.");
              }
              else
              {
                  System.out.println ("Philosopher " + name +
                                      " getting left chopstick.");
                  left.get ();

                  System.out.println ("Philosopher " + name +
                                      " got left chopstick.");
              }

              System.out.println ("Philosopher " + name + " is eating.");

              sleep ((int) (50 * Math.random ()));

              left.put ();
              System.out.println ("Philosopher " + name +
                                  " putting down left chopstick.");

              right.put ();
              System.out.println ("Philosopher " + name +
                                  " putting down right chopstick.");
          } 
          catch (InterruptedException e) {}
       }
   }
}
